Матч 25, Счастливые пятерки (LuckyFives)

Некоторые люди считают пятерку счастливым числом. Они бросают несколько костей, и если пятерка выпадает больше чем в одной пятой части костей, то день считается счастливым.

Бросается dice одинаковых костей, имеющих sides сторон. Необходимо вычислить вероятность того, что день будет счастливым. Вероятность выпадения пятерки при бросании кости с sides сторонами равна 1 / sides.

Класс: LuckyFives

Метод: double probability(int dice, int sides)

Ограничения: 1 £ dice £ 20, 5 £ sides £ 10.

Вход. Количество бросаемых костей dice и количество сторон sides в них.

Выход. Вероятность того, что день будет счастливым.

Пример входа

dice	sides
1	6
5	6
20	10

Пример выхода

0.16666666666666666

0.19624485596707822

0.04317449528446337

РЕШЕНИЕ

вероятность + динамическое программирование

.Заведем двумерный массив p[21][21], в котором p[d][i] равно вероятности выпадения в точности i пятерок при бросании d костей. Занесем в переменную q вероятность выпадения пятерки на кости, состоящей из sides сторон. Изначально обнулим массив p, присвоим p[0][0] = 1 (вероятность выпадения 0 пятерок при бросании 0 костей равна 1).

При бросании d костей выпадет в точности i пятерок, если:

а) после бросания d – 1 кости выпало i пятерок, а на d - ой кости выпала не пятерка. Вероятность этого события равна p[d – 1][i] * (1 – q).

б) после бросания d – 1 кости выпала i – 1 пятерка, а на d - ой кости выпала пятерка. Вероятность этого события равна p[d – 1][i – 1] * q.

Таким образом,

p[d][i] = p[d – 1][i] * (1 – q) + p[d – 1][i – 1] * q

Пересчитаем по этой формуле все значения p[d][i], 1 £ d £ dice, 0 £ i £ dice. День считается удачным, если пятерка выпадет как минимум на dice / 5 + 1 кости (больше чем в одной пятой части). Для нахождения требуемой вероятности остается просуммировать значения p[dice][i] для i от dice / 5 + 1 до dice.

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

double p[21][21];

class LuckyFives

{

public:

double probability(int dice, int sides)

{

double res = 0, q = 1.0/sides;

int d,i;

memset(p,0,sizeof(p));

p[0][0] = 1;

for(d = 1; d <= dice; d++)

for(i = 0; i <= dice; i++)

p[d][i] = p[d-1][i] * (1-q) + p[d-1][i-1] * q;

for(i = dice/5 + 1; i <= dice; i++)

res += p[dice][i];

return res;

}

};